Partition Array Into Two Arrays to Minimize Sum Difference

Statement#

Suppose you are given an array, nums, containing positive numbers. You need to partition the array into two arrays such that the absolute difference between their sums is minimized.

Note: Each element of the nums array should be present in one of the partitioned arrays.

Let’s say you have the following array:

  • [2, 3, 1]

The two partitioned arrays with the minimum difference in their sums are:

  • [2,1],sum=3[2, 1], sum = 3
  • [3],sum=3[3], sum = 3

So, the minimum difference becomes 33=0|3-3| = 0.

Constraints:

  • 11\leq nums.length 900\leq 900
  • 11\leq nums[i] 104\leq 10^4

Examples#

No.

nums

partitioned arrays

mimimum difference

1

[5, 4, 4, 7, 2, 9 ]

[4, 5, 7], [2, 4, 9]

1

2

[3, 25, 4, 12, 2]

[25], [12, 4, 3, 2]

4

3

[3, 7, 4, 12, 2]

[7, 4, 3], [12, 2]

0

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Partition Array Into Two Arrays to Minimize Sum Difference

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

A naive approach is to generate all possible combinations of two arrays from the original array. We then check which combination minimizes the difference between the sums of the two partitioned arrays.

For example, we have the following array of values:

  • nums: [4,7,1][4, 7, 1]

To find the minimum difference, we try all possible combinations:

  • [4],[7,1]=>[4], [7, 1] => Difference =4= 4
  • [7],[4,1]=>[7], [4, 1] => Difference =2= 2
  • [1],[4,7]=>[1], [4, 7] => Difference =10= 10
  • [7,1],[4]=>[7,1], [4] => Difference =4= 4
  • [4,1],[7]=>[4,1], [7] => Difference =2= 2
  • [4,7],[1]=>[4,7], [1] => Difference =10= 10
  • [4,7,1],[]=>[4, 7, 1], [] => Difference =12= 12
  • [],[4,7,1]=>[], [4, 7, 1] => Difference =12= 12

The calculation above shows that we need a recursive solution to make all possible combinations. In other words, we divide the problem into subproblems, and for each array element, we decide whether to place it in the first or second partitioned array. This is done using the following rules:

  • Base case: If we reach the end of the array, and there are no elements to add in either of the partitioned arrays, we return the absolute difference between the sums of the two arrays.

  • Otherwise, we calculate the difference in the sums of the two arrays for the two scenarios:

    • add the current element to the first partitioned array
    • add it to the second partitioned array

We then select the option that results in the minimum difference.

Let’s implement the algorithm as discussed above:

Partition Array Into Two Arrays to Minimize Sum Difference using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is O(2n)O(2^n), where nn is the total number of elements. This is because we have two possible choices for each element, either to include it in the first or the second partitioned array.

Space complexity#

Since we can’t have more than nn recursive calls on the call stack at any time, the space complexity of this approach is O(n)O(n).

Optimized solution using dynamic programming#

Now, let’s improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array. In the recursive approach, the following three variables kept changing:

  • The array index, i.
  • The sum of the first partitioned array, sum1.
  • The sum of the second partitioned array, sum2.

We will use a 2-D table, dp with i rows, and sum1 + 1 columns to store the result, i.e., the difference between the sums of the partitioned arrays. We haven’t considered sum2 since, for a given i and sum1, sum2 of the remaining numbers will always be the same. At any later time, if we encounter the same subproblem, we can return the stored result from the table with an O(1)O(1) look-up instead of re-calculating that subproblem.

Let’s implement the algorithm as discussed above:

Partition Array Into Two Arrays to Minimize Sum Difference using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a 2-D table, the time complexity of this approach is reduced to O(n×S)O(n \times S), where nn is the number of elements in the input array, and SS is the sum of all the elements.

Space complexity#

We now need O(n×S)O(n \times S) space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the Tabulation technique, is an iterative method of solving dynamic programming problems.

Suppose SS is the sum of all the elements in nums. Since we’re taking the absolute difference between the sums of the two partitioned arrays, our minimum difference will always be greater than or equal to 00. Therefore, to minimize the difference, each partitioned array must have a sum as close to (S/2)(S/2) as possible. To make things easier, we only need to ensure that the sum in one partitioned array is as close to (S/2)(S/2) as possible since, then, the remaining sum in the other partitioned array will also become as close to S/2S/2 as possible.

We will initialize a 2-D table of size (n×[(S/2)+1])(n \times [(S/2) + 1]), where nn is the length of nums. This table will have the following properties:

  • Each row i represents the index we’re currently on. It ranges from 00 to nn.

  • Each column s represents the current sum we’re trying to achieve. It ranges from 00 to (S/2)(S/2).

We will iterate the table and fill it with either 11 or 00 depending on if the current sum s can be achieved from the available elements in the partitioned array or not. This is done based on the following rules:

  • We exclude nums[i] from the partitioned array and check whether the sum s can be formed from its previous elements.
if dp[i - 1][s]:
        dp[i][s] = dp[i - 1][s]
  • We include nums[i] in the partitioned array and check whether the sum s can now be formed from its current elements.
 elif s >= nums[i]:
        dp[i][s] = dp[i - 1][s - nums[i]]
  • If neither one of the above two conditions is true, the sum s can not be formed using nums[i]:
else:
    dp[i][s] = 0

After the 2-D table has been filled completely, we will traverse its last row from right to left to find the sum closest to (S/2)(S/2) that the partitioned array can contain. Whenever we find an entry that is 11, the value of i at that entry will be the partitioned array sum. Using this sum we find the sum in the other partitioned array and then calculate their absolute difference.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 The sum S of the nums array is 13. S/2 will be floor(13/2) = 6. So our dp table will be of size (4 x 7).

1 of 23

Created with Fabric.js 3.6.6 The first column will consist of all 1s, since a sums of 0 can always be achieved.

2 of 23

Created with Fabric.js 3.6.6 Each entry in the first row will be 0 because no sum can be generated using nums[0], i.e., 7.

3 of 23

Created with Fabric.js 3.6.6 i = 1, s = 1Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], FALSESo dp[1][1] = 0, since the sum s = 1 can not be formed from the current elements.

4 of 23

Created with Fabric.js 3.6.6 i = 1, s = 2Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[1][2] = dp[0][0] = 1, since the sum s = 2 can be achieved by including nums[1].

5 of 23

Created with Fabric.js 3.6.6 i = 1, s = 3Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[1][3] = dp[0][1] = 0, since the sum s = 3 can not be achieved from the current elements.

6 of 23

Created with Fabric.js 3.6.6 i = 1, s = 4Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[1][4] = dp[0][2] = 0, since the sum s = 4 can not be achieved from the current elements.

7 of 23

Created with Fabric.js 3.6.6 i = 1, s = 5Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[1][5] = dp[0][3] = 0, since the sum s = 5 can not be achieved from the current elements.

8 of 23

Created with Fabric.js 3.6.6 i = 1, s = 6Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[1][6] = dp[0][4] = 0, since the sum s = 6 can not be achieved from the current elements.

9 of 23

Created with Fabric.js 3.6.6 i = 2, s = 1Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[2][1] = dp[1][0] = 1, since the sum s = 1 can be achieved by including nums[2].

10 of 23

Created with Fabric.js 3.6.6 i = 2, s = 2Condition 1: if dp[i - 1][s] == 1, TRUESo dp[2][2] = dp[1][2] = 1, since the sum s = 2 can be achieved by excluding nums[2].

11 of 23

Created with Fabric.js 3.6.6 i = 2, s = 3Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[2][3] = dp[1][2] = 1, since the sum s = 3 can be achieved by including nums[2].

12 of 23

Created with Fabric.js 3.6.6 i = 2, s = 4Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[2][4] = dp[1][3] = 0, since the sum s = 4 can not be achieved from the current elements.

13 of 23

Created with Fabric.js 3.6.6 i = 2, s = 5Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[2][5] = dp[1][4] = 0, since the sum s = 5 can not be achieved from the current elements.

14 of 23

Created with Fabric.js 3.6.6 i = 2, s = 6Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[2][6] = dp[1][5] = 0, since the sum s = 6 can not be achieved from the current elements.

15 of 23

Created with Fabric.js 3.6.6 i = 3, s = 1Condition 1: if dp[i - 1][s] == 1, TRUESo dp[3][1] = dp[2][1] = 1, since the sum s = 1 can be achieved by excluding nums[3].

16 of 23

Created with Fabric.js 3.6.6 i = 3, s = 2Condition 1: if dp[i - 1][s] == 1, TRUESo dp[3][2] = dp[2][2] = 1, since the sum s = 2 can be achieved by excluding nums[3].

17 of 23

Created with Fabric.js 3.6.6 i = 3, s = 3Condition 1: if dp[i - 1][s] == 1, TRUESo dp[3][3] = dp[2][3] = 1, since the sum s = 3 can be achieved by excluding nums[3].

18 of 23

Created with Fabric.js 3.6.6 i = 3, s = 4Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[3][4] = dp[2][1] = 1, since the sum s = 4 can be by achieved by including nums[3].

19 of 23

Created with Fabric.js 3.6.6 i = 3, s = 5Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[3][5] = dp[2][2] = 1, since the sum s = 5 can be achieved by including nums[3].

20 of 23

Created with Fabric.js 3.6.6 i = 3, s = 6Condition 1: if dp[i - 1][s] == 1, FALSECondition 2: if s >= nums[i], TRUESo dp[3][6] = dp[2][3] = 1, since the sum s = 6 can be achieved by including nums[3].

21 of 23

Created with Fabric.js 3.6.6 We will now traverse the last row of dp from right to left to find the first index that contains 1.

22 of 23

Created with Fabric.js 3.6.6 dp[3][6] contains 1, so s = 6 is the sum in one partitioned array. The sum in the other partitioned array will then be 13 - 6 = 7. Hence, the minimum difference in sums will be abs(6 - 7) = 1.

23 of 23

Let’s implement the algorithm as discussed above:

Partition Array Into Two Arrays to Minimize Sum Difference using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we created a 2-D table to store the results of sub-problems that would be used later on, therefore, the time complexity of this approach will also be O(n×[(S/2)+1])O(n \times [(S/2) + 1]).

Space complexity#

We need O(n×[(S/2)+1])O(n \times [(S/2) + 1]) space in memory to store the intermediate values.

Can we do better?#

You must have noticed in the above algorithm that to fill up a row, we only require the previous row’s values; that is, for filling the row against the ithi^{th} element, we require the values from the previous row representing the (i1)th(i-1)^{th} element. Therefore, there is no point in storing the previous (i2)(i - 2) rows.

We can further improve this approach by using a lookup array of length [(S/2)+1])[(S/2) + 1]) instead of creating a table. Next, we update this array for each element using the same calculation which we used earlier.

The time complexity would remain the same, O(n×[(S/2)+1])O(n \times [(S/2) + 1]) , because we still have to do the calculation for each element. The space complexity, however, reduces to O((S/2)+1)O((S/2) + 1) since we are only maintaining an array of size (S/2)+1(S/2) + 1.

Count of Subset Sum

Minimum Number of Refueling Stops